Robinson
Limit pamięci: 256 MB
Rzucony przez sztorm na bezludną wyspę Robinson zbudował łódkę, na
której postanowił wypłynąć w morze i szukać ludzkich siedzib.
Jest on doświadczonym żeglarzem, więc jego łódź jest zbudowana
zgodnie z zasadami sztuki:
ma wzdłużną oś symetrii oraz odpowiedni kształt.
Na dziobie jest wąska, stopniowo rozszerza się w stronę środka,
by z kolei zacząć się zwężać w kierunku rufy.
W szczególności oznacza to, że w pewnym miejscu w środku łódź jest
szersza niż na dziobie i na rufie.
Pech chciał, że w miejscu, w którym Robinson spuścił swoją łódź na
wodę, rosną bardzo gęste trzciny.
Co gorsza, są one tak sztywne, że łódź nie jest w stanie ich
złamać i przepłynąć przez zajmowane przez trzciny miejsca.
Być może odpowiednio manewrując łodzią, Robinson jest w stanie
wypłynąć na otwarte morze.
Ze względu na słabą manewrowość, łódź może się poruszać do przodu,
do tyłu, w prawo oraz w lewo, ale nie może skręcać.
Oznacza to, że może się zdarzyć sytuacja, gdy łódź porusza się
rufą lub którąś burtą do przodu.
Twoim zadaniem jest ocenić, czy Robinson może się wydostać na pełne morze.
Dla uproszczenia, wyspa wraz z otoczeniem jest w zadaniu
reprezentowana przez kwadratową mapę podzieloną na kwadratowe pola
jednostkowe, z których każde może być zajęte przez wodę, kawałek
łodzi Robinsona, bądź przez przeszkodę (np. ląd lub trzcinę).
Łódź jest ustawiona równolegle do jednego z czterech kierunków
Świata i właśnie w tym kierunku przebiega przez środek
łodzi pas pól jednostkowych, idealnie przepołowionych wzdłużną osią symetrii łodzi.
Przyjmujemy, że poza mapą znajduje się otwarte morze.
Robinson może wypłynąć na otwarte morze, jeżeli łódź jest w stanie
w całości opuścić teren pokazany na mapie.
Pojedynczy ruch to przesunięcie się łodzi o jedno pole w
wybranym kierunku (północ, południe, wschód lub zachód).
Aby ruch był wykonalny, przed i po wykonaniu ruchu łódź musi w
całości znajdować się na wodzie.
Zadanie
Zadanie polega na napisaniu programu, który:
-
wczyta ze standardowego wejścia opis mapy,
-
obliczy minimalną liczbę ruchów łodzi potrzebnych do
wypłynięcia poza obszar pokazany na mapie,
-
wypisze obliczoną liczbę na standardowe wyjście.
Wejście
Pierwszy wiersz zawiera jedną liczbę całkowitą
, oznaczającą długość boku mapy.
W każdym z następnych wierszy znajduje się po znaków
opisujących kolejne pola mapy:
-ty znak w wierszu numer określa zawartość pola o
współrzędnych .
W wierszu mogą się pojawić następujące znaki:
- "." - (kropka) oznacza pole zajęte przez wodę,
- "X" - oznacza przeszkodę (trzcinę lub kawałek lądu),
- "r" - oznacza fragment łodzi Robinsona.
Wyjście
Twój program powinien wypisać (w pierwszym i jedynym wierszu
standardowego wyjścia) jedną dodatnią liczbę całkowitą, równą
najmniejszej koniecznej liczbie ruchów łodzi niezbędnych do
opuszczenia przez łódź w całości terenu przedstawionego na
mapie.
Jeśli wypłynięcie na otwarte morze nie jest możliwe,
należy wypisać słowo "NIE".
Przykład
Dla danych wejściowych:
10
..........
..........
..r.......
.rrrX.....
rrrrr.....
.rrr......
X.r.......
.Xr.......
..........
..........
poprawną odpowiedzią jest:
10
Autor zadania: Karol Cwalina.